package com.liuzhilong.infrastructure.framework.algorithms.datastruct.graph.algorithms.mst;

import com.liuzhilong.infrastructure.framework.algorithms.datastruct.graph.Edge;
import com.liuzhilong.infrastructure.framework.algorithms.datastruct.graph.Graph;
import com.liuzhilong.infrastructure.framework.algorithms.datastruct.graph.Vertex;
import com.liuzhilong.infrastructure.framework.algorithms.datastruct.line.PriorityQueue;

import java.util.List;


/**
 * <h1>Kruskal算法</h1>
 *<p>
 *     Kruskals算法的和Prim不同，是从Edge的角度进行设计的。但是他们核心的原理都是一套。即切分原理。
 *</p>
 * <p>算法思想：把边全部放入优先级队列中，每次获取最小的边，判断是否有环生成 ，如果没有环，则这条边就属于最小生成树的边。</p>
 */
public class KruskalMST <T>{
    private Graph<T> graph;
    private List<Edge<T>> mst;

    private PriorityQueue<Edge<T>> priorityQueue;

    public Iterable<Edge<T>> mst(){
        return mst;
    }




    private KruskalMST<T> init(){

        this.graph.getVertices().forEach((key,value)->{
            value.getNext().forEach(this.priorityQueue::insert);
        });

        int endSize = this.graph.getVertices().keySet().size() - 1;
        while (!this.priorityQueue.isEmpty() && this.mst.size() < endSize) {
            Edge<T> min = this.priorityQueue.pull();
            if(!isCycle(min.getFrom(),min.getTo())){
                union(min.getFrom(),min.getTo());
                mst.add(min);
            }
        }

        return this;
    }

    /**
     *  判断如果连接顶点{@code v1}和{@code v2}是否会造成环。
     *  在实际的使用中，可以是用连通分量来实现。每次向{@code mst}添加一个边的时候，进行相关两个顶点的联通分量设置。
     *  这个方法其实等价于{@code v1}和{@code v2}是否是一个联通分量。
     *
     *  TODO 使用连通分量实现
     * @return
     */
    private boolean isCycle(Vertex<T> v1,Vertex<T> v2){
        if(1==1){
            throw new UnsupportedOperationException("方法为实现，期待联通分量的树结构");
        }
        return false;
    }
    //连通
    //TODO
    private void union(Vertex<T> v1,Vertex<T> v2){



    }


    /**
     * @param vertex
     */
    private void visit(Vertex<T> vertex){

    }


    private KruskalMST(Graph<T> graph){
        this.graph = graph;
    }

    public static <T> KruskalMST<T> create(Graph<T> graph){
        return new KruskalMST<>(graph).init();
    }







}
